package offer.day29;

import java.util.Arrays;

public class No49GetUglyNumber_UseSpace {
    /*
     * 面试49:丑数     计算每一个丑数的值存入数组，求得第N个丑数
     * 题目:把只包含因子2,3,5的数称作丑数(Ugly Number).
     * 求按从小到大的排序的第1500个丑数.
     * 例如,6,8都是丑数,但14不是,因为它包含银子7.
     * 习惯上把1当作第一个丑数
     *
     * 思路:使用空间换时间的概念
     * 构造一个数组 存储丑数  计算从小到大的丑数
     * 因为丑数的定义是2，3，5因子，所以 是由2，3，5相乘得到的
     * 需要记录2，3，5都已经乘到哪一索引处，indexOf2，indexOf3，indexOf5然后每次乘玩的结果进行比较
     * uglyArray[indexOf]*2 ,uglyArray[indexOf3]*3,uglyArray[indexOf5]*5去最小的存入丑数数组中
     * 然后判断是哪一个完成了相乘，将其index位置，向后移动一个
     * 然后接着找下一个丑数，直到找到第N个丑数为止，返回即可
     *
     * 优点：时间效率高，很快就能出来结果
     * 缺点：空间换时间，利用了辅助空间
     *
     * */
    public static void main(String[] args) {
        No49GetUglyNumber_UseSpace g = new No49GetUglyNumber_UseSpace();
        System.out.println("从小到大的顺序排列的第15个丑数是:"+g.GetUglyNumber(15));
//        System.out.println("从小到大的顺序排列的第1500个丑数是:"+g.GetUglyNumber(1500));

    }

    private int GetUglyNumber(int index) {
        if(index<=0) return -1;
        int count=1;
        int[] uglyArray=new int[index];
        uglyArray[0]=1;
        int index2=0;
        int index3=0;
        int index5=0;
        int number2,number3,number5;
        while(count<index){
            number2=uglyArray[index2]*2;
            number3=uglyArray[index3]*3;
            number5=uglyArray[index5]*5;
            int min=GetMin(number2,number3,number5);
            if(min==number2){
                index2++;
            }
            if(min==number3){
                index3++;
            }
            if(min==number5){
                index5++;
            }
            uglyArray[count++]=min;
        }
        System.out.println(Arrays.toString(uglyArray));
        return uglyArray[count-1];
    }

    private int GetMin(int number1,int number2,int number3){
        int min= Math.min(number1,number2);
        min= Math.min(min,number3);
        return min;
    }
}
